import java.util.*;
/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 */


 /**
 *  AC
 * time：96.2 mem：54.31
 * 
 * 
 */

// @lc code=start
class Solution {
    ArrayList<String> ret = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        bt(new StringBuilder(),0,0,n);
        return ret;
    }

    void bt(StringBuilder sb,int l,int r,int total){
        if(l==total){
            for(int i = r;i<total;i++){
                sb.append(")");
            }
            ret.add(sb.toString());
            sb.delete(l+r, total*2);
            return;
        }

        bt(sb.append("("),l+1,r,total);
        sb.deleteCharAt(sb.length()-1);
        if(r!=l){
            bt(sb.append(")"),l,r+1,total);
            sb.deleteCharAt(sb.length()-1);
        }

    }
}
// @lc code=end



